package 栈和队列;

import java.util.Stack;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-02
 */
public class 最大矩阵栈实现 {
    class StackItem {
        public int height;
        public int index;

        public StackItem(int height, int index) {
            this.height = height;
            this.index = index;
        }
    }
    public int maxRectangle(int[] height) {
        int maxarea = 0; //当前最大面积
        int area = 0;//当前区域面积
        int left;//当前区域左边界
        int right;//当前区域右边界
        for(int i=0; i<height.length; i++){
            left = i; //初始化左边界
            right = i; //初始化右边界
            while(left>0 && height[left-1] >= height[i]){
                left--; //找到当前区域左边界
            }
            while(right<height.length-1 && height[right+1] >= height[i]){
                right++; //找到当前区域右边界
            }
            area = height[i] * (right-left+1);
            if(area > maxarea){
                maxarea = area;
            }
        }
        return maxarea;
    }
    int maxRectangleArea(int[] arr, int n) {
        int maxArea = 0;
        if (arr == null || arr.length == 0) {
            return maxArea;
        }
        Stack<StackItem> stack = new Stack<>();
        stack.push(new StackItem(Integer.MIN_VALUE, -1));
        for (int i = 0; i <= n; i++) {
            StackItem cur = new StackItem(i < n ? arr[i] : Integer.MIN_VALUE, i);
            if (cur.height >= stack.peek().height) {
                stack.push(cur);
                continue;
            }
            while (stack.size() > 1) {
                StackItem prev = stack.peek();
                int area = (i - prev.index) * prev.height;
                if (area > maxArea) {
                    maxArea = area;
                }
                prev.height = cur.height;
                if (prev.height > stack.get(stack.size() - 2).height) {
                    break;
                }
                stack.pop();
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        最大矩阵栈实现 stackMaxMatrix = new 最大矩阵栈实现();
        System.out.println(stackMaxMatrix.maxRectangleArea(new int[]{1, 1, 1, 4, 2}, 5));
    }
}